/**
 * 给定数组A，求满足条件的子序列的数量
 * 条件：子序列中不存在连续三个奇偶相同的元素
 * 
 * 设JJ/JO/OJ/OO分别是以i结尾的且末尾是奇奇、奇偶、偶奇、偶偶的子序列数量
 * J、O是以i结尾且末尾是奇、偶的数量
 * Dxx则是区间[0...i]以内对应的数量
 * 且令CJ与CO是[0...i]以内奇数和偶数分别的数量
 * 
 * 如果Ai是奇数，则
 * JJ[i] = DOJ[i - 1] + CJ[i - 1] 当前奇数配上以前所有的DOJ或者CJ均可以形成合法的JJ
 * OJ[i] = DO[i - 1] 当前奇数配上以前所有DO可以形成合法的OJ
 * J[i] = OJ[i] + JJ[i] + 1 当前以奇数结尾的数量分为三个部分，以OJ结尾的，以JJ结尾的，以及单独的当前数自己
 * 其余以O结尾的显然全为0
 * 
 * 如果Ai是偶数，与上述类似
 * 
 * 至于DXX，根据Ai的奇偶性照抄或者累加即可
 */

using llt = long long;
using vll = vector<llt>;
const llt MOD = 1E9 + 7;

class Solution {

int N;
vll JJ, JO, OJ, OO; // 结尾
vll DJJ, DJO, DOJ, DOO; // 以内
vll J, O; // 结尾
vll DJ, DO; // 以内

public:
    int countStableSubsequences(vector<int>& nums) {
        N = nums.size();

        JJ.assign(N + 1, 0);
        JO.assign(N + 1, 0);
        OJ.assign(N + 1, 0);
        OO.assign(N + 1, 0);

        DJJ.assign(N + 1, 0);
        DJO.assign(N + 1, 0);
        DOJ.assign(N + 1, 0);
        DOO.assign(N + 1, 0);        
        
        J.assign(N + 1, 0);
        O.assign(N + 1, 0);

        DJ.assign(N + 1, 0);
        DO.assign(N + 1, 0);

        int cj = 0, co = 0;
        
        for(int i=1;i<=N;++i){
            DJJ[i] = DJJ[i - 1];
            DJO[i] = DJO[i - 1];
            DOJ[i] = DOJ[i - 1];
            DOO[i] = DOO[i - 1];
            DJ[i] = DJ[i - 1];
            DO[i] = DO[i - 1];

            auto vi = nums[i - 1];
            if(vi & 1){
                JJ[i] = (DOJ[i - 1] + cj) % MOD;
                OJ[i] = DO[i - 1];
                J[i] = (OJ[i] + JJ[i] + 1) % MOD;
                cj += 1;

                (DJJ[i] += JJ[i]) %= MOD;
                (DOJ[i] += OJ[i]) %= MOD;
                (DJ[i] += J[i]) %= MOD; 
            }else{
                JO[i] = DJ[i - 1];
                OO[i] = (DJO[i - 1] + co) % MOD;
                O[i] = (JO[i] + OO[i] + 1) % MOD;
                co += 1;

                (DJO[i] += JO[i]) %= MOD;
                (DOO[i] += OO[i]) %= MOD;
                (DO[i] += O[i]) %= MOD; 
            }
        }
        
        return (DJ[N] + DO[N]) % MOD;
    }
};©leetcode